前天分享到面對龐大的對局樹時，我們不要跟他拚拳，而是嘗試切他節點，除了Alpha-Beta Pruning之外，今天要再來介紹一個新的演算法。

Scout Algorithm

Scout（斥候）根據教育部國語辭典的解釋是指「負責偵察敵情的哨兵」，例如先派斥候判斷敵方兵力，如果比我方多就趕緊撤，比我方少就大軍出動，在搜索演算法中也是，用Scout來評估是否有必要深入搜索某分支，如果這個分支很有潛力，那我就花資源下去搜索，如果已經確定這個分支並不會比現有分支好，那就可以果斷剪枝，藉此提高搜索效率，減少不必要的節點探索。

如下圖所示，假設我們已經確定某個節點的分數為 8，如果存在一個更有效率的方法可以判斷 A 節點 的分數不大於 8，那麼我們就可以直接忽略對 A 節點 的進一步搜索。

當然這種有效的方法必須比完全搜索 A 節點來計算真實值更快，不然直接搜索完不就好了?!

Scout 的工作流程如下：

1. 首先對第一個子節點進行完整搜索，得到評估值 8。
2. 接著對 A 節點進行快速評估：
   • 如果 A 節點的最大可能值不會超過 8，則可以直接剪枝，避免對 A 節點進行深入搜索。
   • 如果 A 節點有機會超過 8，則必須對 A 節點進行完整搜索，以確定其真實分數。
3. 對 B 節點進行相同的判斷，重複上述步驟。

用世紀帝國中的斥候做比喻，斥候是一種速度快、視野廣的單位，用來快速探測地形和敵情。
在世紀帝國中，你不會一開始就用村民進行全地圖的探索，村民移動慢且應該優先讓他們去採集。大家都會派出斥候去偵察，根據地形來決定應該搜索的區域。例如，當斥候遇到河流之類的障礙時，判斷該方向不值得深入探索（相當於剪枝），你會迅速轉向其他可能有資源或敵方基地的區域。
Scout 演算法的快速評估就像派出斥候一樣，通過先驗判斷來決定是否深入某個方向。這樣的搜索方式比直接對每個可能的選項進行全局搜索（相當於讓村民去探索整個地圖）要高效得多，節省了大量資源與時間。

效能分析

這邊我們與Alpha-Beta Pruning做個比較。
下圖為Scout搜索的節點數比Alpha-Beta Pruning少的例子。

下圖為Scout搜索的節點數比Alpha-Beta Pruning多的例子。

只要Scout沒能發揮出作用的情況下，那還是得拜訪過所有的節點，比起Alpha-Beta Pruning還會額外增加評估節點的成本，有些節點會被重複拜訪。

實作

def scout(board, depth, current_player, maximizing_player, alpha, beta):
    winner = board.check_winner()
    if winner is not None or depth == 0:
        if winner == maximizing_player:
            return 1
        elif winner == 'Draw':
            return 0
        elif winner is not None:
            return -1

    opponent = 'O' if current_player == 'X' else 'X'
    first_move = True

    if current_player == maximizing_player:  # max層
        for move in board.get_available_moves():
            board.set_move(move, current_player)
            if first_move:
                # 第一次完整搜索
                score = scout(board, depth - 1, opponent,
                              maximizing_player, alpha, beta)
                first_move = False
            else:
                # Scout 搜索: 測試該分支是否有潛力
                score = scout(board, depth - 1, opponent,
                              maximizing_player, alpha, alpha + 1)
                if alpha < score < beta:
                    # 如果該分支有潛力，再進行完整搜索
                    score = scout(board, depth - 1, opponent,
                                  maximizing_player, alpha, beta)

            board.undo_move(move)
            alpha = max(alpha, score)

            if alpha >= beta:  # Beta 剪枝
                break

        return alpha
    else:  # min層
        for move in board.get_available_moves():
            board.set_move(move, current_player)
            if first_move:
                # 第一次完整搜索
                score = scout(board, depth - 1, opponent,
                              maximizing_player, alpha, beta)
                first_move = False
            else:
                # Scout 搜索: 測試該分支是否有潛力
                score = scout(board, depth - 1, opponent,
                              maximizing_player, beta - 1, beta)
                if alpha < score < beta:
                    # 如果該分支有潛力，再進行完整搜索
                    score = scout(board, depth - 1, opponent,
                                  maximizing_player, alpha, beta)

            board.undo_move(move)
            beta = min(beta, score)

            if alpha >= beta:  # Alpha 剪枝
                break

        return beta

Nega Scout

Scout也跟Minimax還有Alpha-Beta一樣有Nega版本的。

def scout(board, depth, current_player, alpha, beta):
    winner = board.check_winner()
    if winner is not None or depth == 0:
        if winner == maximizing_player:
            return 1
        elif winner == 'Draw':
            return 0
        elif winner is not None:
            return -1
    
    opponent = 'O' if current_player == 'X' else 'X'
    
    first_move = True
    for move in board.get_available_moves():
        board.set_move(move, current_player)
        if first_move:
            # 第一次要進行完整搜索
            score = -scout(board, depth - 1, opponent, -beta, -alpha)
            first_move = False
        else:
            # Scout Search: 只進行快速搜索，確定是否值得進行完整搜索
            score = -scout(board, depth - 1, opponent, -alpha - 1, -alpha)
            if alpha < score < beta:
                # 如果快速搜索顯示該分支有潛力，進行完整評估
                score = -scout(board, depth - 1, opponent, -beta, -alpha)
        
        board.undo_move(move)
        
        # 更新 alpha 值，並進行剪枝
        alpha = max(alpha, score)
        if alpha >= beta:
            break
    
    return alpha